package com.s10.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * r-b tree 实现
 * @author acc8226
 */
public class RedBlackTree<T> {

	/**
	 * The number of nodes in the tree
	 */
	private transient int size = 0;

	private Node<T> root;

	public void insert(T data) {
		Node<T> p = this.root;
		if (p == null) {
			this.root = new Node<>(data, null);
			size = 1;
			return;
		}
		@SuppressWarnings("unchecked")
		Comparable<? super T> t = (Comparable<? super T>) data;
		int cmp;
		Node<T> parent;
		do {
			parent = p;
			cmp = t.compareTo(p.data);
			if (cmp < 0) {
				p = p.left;
			} else {
				p = p.right;
			}
		} while (p != null);
		Node<T> node = new Node<>(data, parent);
		if (cmp < 0) {
			parent.left = node;
		} else {
			parent.right = node;
		}
		this.fixAfterInsertion(node);
		size++;
	}

	public T delete(T data) {
		Node<T> node = this.find(data);
		// 没有找到返回 null
		if (node == null) {
			return null;
		}
		T oldValue = node.data;
		this.deleteNode(node);
		return oldValue;
	}

	public Node<T> find(T data) {
		if (data == null) {
			throw new NullPointerException();
		}
		@SuppressWarnings("unchecked")
		Comparable<? super T> t = (Comparable<? super T>) data;
		Node<T> p = this.root;
		while (p != null) {
			if (data == p.data) {
				return p;
			}
			if (t.compareTo(p.data) < 0) {
				p = p.left;
			} else {
				p = p.right;
			}
		}
		return null;
	}

	public int size() {
		return this.size;
	}

	// 按层遍历
	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		builder.append("RedBlackTree [").append("\n");
		Node<T> node = this.root;
		if (node != null) {
			Queue<Node<T>> queue = new LinkedList<>();
			queue.add(node);

			while (!queue.isEmpty()) {
				int size = queue.size();
				for (int i = 0; i < size; i++) {
					Node<T> removedNode = queue.remove();
					builder.append(removedNode + " ");

					if (removedNode.left != null) {
						queue.add(removedNode.left);
					}
					if (removedNode.right != null) {
						queue.add(removedNode.right);
					}
				}
				builder.append("\n");
			}
		}
		builder.append("]");
		return builder.toString();
	}

	private void deleteNode(Node<T> p) {
		this.size--;

		// 要删除的节点有两个子节点
		if (p.left != null && p.right != null) {
			Node<T> s = successor(p);
			p.data = s.data;
			p = s;
		}
		// 将会替换 p 的位置
		Node<T> replacement = (p.left != null ? p.left : p.right);
		if (replacement != null) {
			// Link replacement to parent
			replacement.parent = p.parent;
			if (p.parent == null)
				this.root = replacement;
			else if (p == p.parent.left)
				p.parent.left = replacement;
			else
				p.parent.right = replacement;

			// Null out links so they are OK to use by fixAfterDeletion.
			p.left = p.right = p.parent = null;
			// 当前待删除节点是红色的，它被删除之后不会造成任何破坏影响。否则就需要进行进一步调整
			// Fix replacement
			if (p.color == BLACK)
				fixAfterDeletion(replacement);
		}
		// return if we are the only node.
		else if (p.parent == null) {
			this.root = null;
		}
		// No children. Use self as phantom replacement and unlink.
		else {
			if (p.color == BLACK)
				fixAfterDeletion(p);
			if (p.parent != null) {
				if (p == p.parent.left)
					p.parent.left = null;
				else if (p == p.parent.right)
					p.parent.right = null;
				p.parent = null;
			}
		}
	}

	// 寻找该节点的后继节点
	private Node<T> successor(Node<T> t) {
		if (t == null)
			return null;
		// 右子节点中数值最小的节点
		else if (t.right != null) {
			Node<T> p = t.right;
			while (p.left != null)
				p = p.left;
			return p;
		} else {
			Node<T> p = t.parent;
			Node<T> ch = t;
			while (p != null && ch == p.right) {
				ch = p;
				p = p.parent;
			}
			return p;
		}
	}

	/**
	 * 调整红黑树：变色 + 左右旋操作
	 */
	private void fixAfterInsertion(Node<T> node) {
		// 规定插入的节点必定为叶子节点 且 为红色
		node.color = RED;
		// 插入节点的父节点是黑色的，仍然满足红黑树定义，什么都不用做。否则表示父节点红色进入循环
		while (node != null && node != this.root && node.parent.color == RED) {
			Node<T> parent = node.parent;
			Node<T> grandParent = parent.parent;
			Node<T> uncle = grandParent.left == parent ? grandParent.right
					: grandParent.left;
			// 情况 1: 父节点红色, 叔叔节点同是红色
			if (uncle != null && uncle.color == RED) {
				// 为叔叔、父节点、祖父节点设置颜色
				parent.color = uncle.color = BLACK;
				grandParent.color = RED;
				// 关注点改为 祖父节点
				node = grandParent;
			}
			// 情况 2: 父节点为红色, 叔叔节点是黑或 null
			else {
				if (grandParent.left == parent) {
					// grandParent.left.right 为该节点，对应分别插入 5 2 3 的情况
					if (parent.right == node) {
						// node 节点改变
						node = node.parent;
						this.rotateLeft(node);
					}
					// grandParent.left.right 为该节点，分别插入 5 3 2 的情况
					this.rotateRight(grandParent);
				} else {
					// grandParent.right.left 为该节点，对应分别插入 2 5 3 的情况
					if (parent.left == node) {
						// node 节点改变
						node = node.parent;
						this.rotateRight(node);
					}
					// grandParent.right.right 为该节点 ，对应分别插入 2 3 5 的情况
					this.rotateLeft(grandParent);
				}
				// 父节点红变黑
				node.parent.color = BLACK;
				// 旋转前的祖父节点 将变成了 新的兄弟节点 黑变红
				grandParent.color = RED;
			}
		}
		root.color = BLACK;
	}

	// 删除的二次调整
	private void fixAfterDeletion(Node<T> x) {
		// x 不是 root 节点且为黑色
		while (x != root && x.color == BLACK) {
			Node<T> parent = x.parent;
			Node<T> sibling;
			// x 是父节点的左孩子
			if (x == parent.left) {
				sibling = parent.right;
				// case 1：兄弟节点为红色（其实隐含了当前节点和它的父节点是黑色的，而它的兄弟节点是红色）
				// 节点x的父节点左旋，
				// 然后父节点颜色变成红色
				// 而原来的兄弟节点变成黑色
				// 关注节点不变
				if (sibling.color = RED) {
					parent.color = RED;
					sibling.color = BLACK;
					this.rotateLeft(parent);
					sibling = x.right;
				}
				// 兄弟节点，包括兄弟节点的所有子节点都是黑色
				if (BLACK == colorOf(leftOf(sibling))
						&& BLACK == colorOf(rightOf(sibling))) {
					// 兄弟节点设置为红色
					setColor(sibling, RED);
					// 节点指向它的父节点
					x = parent;
				}
				// 兄弟节点的所有子节点至少有一个是红色【红 黑 | 黑 红 | 红 红】
				else {
					// 仅 红 黑 的情况
					if (BLACK == colorOf(rightOf(sibling))) {
						// 兄弟节点改为红色
						setColor(sibling, RED);
						// 兄弟的左子节点改为黑色
						setColor(leftOf(sibling), BLACK);
						// 围绕关注节点的兄弟节点右旋；
						this.rotateRight(sibling);
						sibling = parent.right;
					}
					setColor(sibling, colorOf(parent));
					setColor(parent, BLACK);
					setColor(rightOf(sibling), BLACK);
					rotateLeft(parent);
					x = this.root;
				}
			} else {
				sibling = parent.left;
				if (sibling.color = RED) {
					parent.color = RED;
					sibling.color = BLACK;
					this.rotateRight(parent);
					sibling = x.left;
				}
				// 兄弟节点，包括兄弟节点的所有子节点都是黑色
				if (BLACK == colorOf(rightOf(sibling))
						&& BLACK == colorOf(leftOf(sibling))) {
					// 兄弟节点设置为红色
					setColor(sibling, RED);
					// 节点指向它的父节点
					x = parent;
				}
				// 兄弟节点的所有子节点至少有一个是红色【红 黑 | 黑 红 | 红 红】
				else {
					// 仅 黑 红的情况
					if (BLACK == colorOf(leftOf(sibling))) {
						// 兄弟节点改为红色
						setColor(sibling, RED);
						// 兄弟的左子节点改为黑色
						setColor(rightOf(sibling), BLACK);
						// 围绕关注节点的兄弟节点右旋；
						this.rotateLeft(sibling);
						sibling = parent.left;
					}
					setColor(sibling, colorOf(parent));
					setColor(parent, BLACK);
					setColor(leftOf(sibling), BLACK);
					rotateRight(parent);
					x = this.root;
				}
			}
		}
		x.color = BLACK;
	}

	// 左旋：假设 x 是父节点, y 是 x 的 右子节点
	private void rotateLeft(Node<T> x) {
		Node<T> y = x.right;
		// x.right
		x.right = y.left;
		if (x.right != null) {
			// x.right 一个来回
			x.right.parent = x;
		}
		// x.parent 转移到 y.parent 一个来回
		y.parent = x.parent;
		if (y.parent == null) {
			this.root = y;
		} else if (y.parent.left == x) {
			y.parent.left = y;
		} else {
			y.parent.right = y;
		}
		// y.left 一个来回
		y.left = x;
		x.parent = y;
	}

	// 右旋：假设 x 是父节点, y 是 x 的 左子节点
	private void rotateRight(Node<T> x) {
		Node<T> y = x.left;
		x.left = y.right;
		if (x.left != null) {
			x.left.parent = x;
		}
		y.parent = x.parent;
		if (y.parent == null) {
			this.root = y;
		} else if (y.parent.left == x) {
			y.parent.left = y;
		} else {
			y.parent.right = y;
		}
		y.right = x;
		x.parent = y;
	}

	private static final boolean RED = false;
	private static final boolean BLACK = true;

	private static <T> Node<T> leftOf(Node<T> p) {
		return (p == null) ? null : p.left;
	}

	private static <T> Node<T> rightOf(Node<T> p) {
		return (p == null) ? null : p.right;
	}

	private static <T> boolean colorOf(Node<T> p) {
		return (p == null ? BLACK : p.color);
	}

	private static <T> void setColor(Node<T> p, boolean c) {
		if (p != null) {
			p.color = c;
		}
	}

	static final class Node<T> {
		T data;

		Node<T> left;
		Node<T> right;
		/**
		 * 增加一个指向父节点的引用，会带来极大的便利. 当根结点的父结点为 null
		 */
		Node<T> parent;

		/**
		 * "black" 黑 "red" 红
		 */
		boolean color = BLACK;

		public Node(T data) {
			this.data = data;
		}

		Node(T data, Node<T> parent) {
			this.data = data;
			this.parent = parent;
		}

		@Override
		public String toString() {
			boolean hasParent = this.parent != null;
			boolean hasLeft = this.left != null;
			boolean hasRight = this.right != null;
			return "[" + (color ? "Black" : "Red") + " node, data is "
					+ this.data + (hasParent ? ", hasParent" : ", isRoot")
					+ (hasLeft ? "、hasLeft" : "")
					+ (hasRight ? "、hasRight" : "") + "]";
		}
	}
}
